package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/25 12:57
 *
 二叉树的下一个节点：
 法1：找到根节点进行遍历，使用哈希表，存放<now，pre>
 法2：不使用哈希表，使用遍历即可
 */

public class Main11 {
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

    TreeLinkNode pre;
    TreeLinkNode pNode,ans;
    public void inDfs(TreeLinkNode root){
        if(root==null)return;
        inDfs(root.left);
        if(pre==pNode){
            ans=root;
        }
        pre=root;
        inDfs(root.right);
    }

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode==null)return null;
        TreeLinkNode root=pNode;
        while(root.next!=null){
            root=root.next;
        }
        inDfs(root);
        return ans;
    }


}
